//最短路径 此为图的spfa算法，在不规定一条边（u,v) 的起点小于终点（u<v）的情形下也可以计算正确结果 
//如果规定一条边（u,v) 的起点小于终点（u<v），可以简单地按点的反向顺序进行动态规划

#include <iostream>
#include <climits>
#include <queue>
using namespace std;
const int MAXN=20;
int n;
int cost[MAXN+1][MAXN+1];
int mincost[MAXN+1];//mincost[i]表示城市i到城市n的最省费用
int nextindex[MAXN+1];//nextindex[i]最省费用路径中，下一个城市的编号 
queue<int> qu;
bool in[MAXN+1];
void spfa(int s){
    qu.push(s);
    in[s]=true;
    while(!qu.empty()){
        int u=qu.front();
        qu.pop();
        in[u]=false;
        for(int v=1;v<=n;v++){
            if ((v!=u)&&(cost[v][u]>0)){
                if (cost[v][u]+mincost[u]<mincost[v]){
                    mincost[v]=cost[v][u]+mincost[u];
                    nextindex[v]=u;
                    if (!in[v]) {
                        qu.push(v);
                        in[v]=true;
                    }
                }
            }
        }
    }
}

int main(){
    cin>>n;
    for(int u=1;u<=n;u++)
        for(int v=1;v<=n;v++) cin>>cost[u][v];
    
    for(int u=1;u<=n;u++) mincost[u]=INT_MAX;
    mincost[n]=0;
    nextindex[n]=0;

    spfa(n);
    cout<<mincost[1]<<endl;
    int u=1;
    while(u>0){
        cout<<u<<' ';
        u=nextindex[u];
    }
}